iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 7
0
自我挑戰組

透過JavaScript學習演算法與資料結構系列 第 7

合併排序法(Merge Sort)

  • 分享至 

  • xImage
  •  

主要是將陣列一分為二區分成左右陣列,直到只有一個元素才停止,接著逐一將左右陣列的第一個值互相比大小,小的值放到新陣列再把大的值放在它的後面,新的陣列完成後再跟上一層未做排序合併的陣列跑一次剛剛的動作,就這樣從分割到合併就形成這套演算法。

先看這部有趣的影片
Yes

請執行這段程式並看程式中的log,log中的變化與影片中人物的移動是一樣的,希望可以幫助到大家,程式碼如下:

// Split the array into halves and merge them recursively 
function mergeSort (arr) {
  // return once we hit an array with a single item
  if (arr.length === 1) {
    return arr
  }

  const middle = Math.floor(arr.length / 2) 
  const leftArr = arr.slice(0, middle) 
  const rightArr = arr.slice(middle)
  console.log('leftArr',leftArr);
  console.log('rightArr',rightArr);
  return merge(mergeSort(leftArr),mergeSort(rightArr))
}

// compare the arrays item by item and return the concatenated sortedArr
function merge (leftArr, rightArr) {
  const sortedArr = [];

  while (leftArr.length && rightArr.length) {
    console.log(`${leftArr[0]} compare with ${rightArr[0]}`)
    if (leftArr[0] < rightArr[0]) {
      sortedArr.push(leftArr.shift())
    } else {
      sortedArr.push(rightArr.shift())
    }
  }
  console.log('**sortedArr**',[...sortedArr,...leftArr,...rightArr]);
  return [...sortedArr,...leftArr,...rightArr];
}

const arr=[4,2,8,6,0,5,1,7,3,9];
console.log(mergeSort(arr));

完整的程式碼


上一篇
希爾排序法(Shell Sort)
下一篇
快速排序法(Quick Sort)
系列文
透過JavaScript學習演算法與資料結構30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言